$R(5,5)\leq 48$
March 30, 2017
7:46 AM
For the purpose of this discussion, any pair of people in the world either
love each other or hate each other, and the feelings are always mutual.
Within a group of people, can you always find a triple such that they all
love each other or all hate each other?
If the group is size 4, the answer is no. Arrange the people in a square,
and it may be that each person loves her neighbors but hates the people
diagonally away from her. Within such an arrangement you cannot find a
love triangle, nor a hate triangle.
The exact same thing works for pentagons (see e.e. the first image at
[link]), but fails to work for
hexagons, because in a hexagon you can find a triangle made entirely of
diagonals, so there would be a hate triangle.
Indeed it is not too hard to show that within a group of six people you
will always find either a love triangle or a hate triangle. In Ramsey
Theory Talk, R(3,3)=6.
Suppose now you had a party with n people and you wanted to find a love
square or a hate square - a group of four people who all love each other
or all hate each other. It turns out that in a party of 18 people this is
always possible, yet in a party of 17 it may not be possible. In Ramsey Theory
Talk, R(5,5)=18.
An old theorem of Ramsey says that for any k, R(k,k) exists. In other
words, given k, in a large enough party you will always be able to find a
group of k people who all love each other or who all hate each other. But
Ramsey does not tell us what the number R(k,k) really is. As per the
discussion above, R(3,3)=6 and R(5,5)=18, but other than that and the even
smaller cases (which are silly), no other R(k,k) number is known.
The title of Brendan's paper, "R(5,5)<=48", sufficiently explains the main
part of what he did (with Angeltveit). See
[link].
The problem is hard because the number of possible relationships to
inspect within a given party grows very rapidly as the size of the party
grows. Hence one has to be *very* clever about how to study parties with
around 50 participants *without* having to inspect all possible
relationships between them. Even then, when cleverness runs its course, it
remains a huge computational challenge. I think the real interest in
Brendan's result is not so much in it in itself, but more in the
cleverness that was employed.
Gil Kalai: [link]